package dp.子序列;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 交错字符串97.java
 * @createTime 2024年03月05日 16:31:00
 */
public class 交错字符串97 {
	/*
    题目隐藏含义：s1和s2长度和为s3,
    重复子问题：
    函数dp(s1,i,s2,j)表示的是s1的前i个字符，能否组成s3的前i+j个字符
    状态方程：
    如果dp[i-1][j]=true，并且s1 [ i - 1] == s3 [ i + j - 1]那么dp [ i ] [ j ] = true 。
    如果 dp [ i ] [ j - 1 ] == true，并且 s2 [ j - 1] == s3 [ i + j - 1]， dp [ i ] [ j ] = true
    其余的dp[i][j]=false;
    baseCase：
    如果 i 为 0，或者 j 为 0，那直接判断 s2 和 s3 对应的字母或者 s1 和 s3 对应的字母即可。
    s1和s2长度为s3
     */
	public boolean isInterleave(String s1, String s2, String s3) {
		if (s1.length() + s2.length() != s3.length()) {
			return false;
		}
		boolean[][] dp = new boolean[s1.length()+1][s2.length()+1];
		for (int i = 0; i <= s1.length(); i++) {
			for (int j = 0; j <= s2.length(); j++) {
				if (i == 0 && j == 0) {
					dp[i][j] = true;
				} else if (i == 0) {
					dp[i][j] = dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
				} else if (j == 0) {
					dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i - 1);
				} else {
					dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
							|| (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
				}
			}
		}
		return dp[s1.length()][s2.length()];
	}
}
